/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 */
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    /**
     * 递归解法
     * 比如1->2->3->NULL
     * 向下递归中
     * node = 1, pre = NULL
     * node = 2, pre = 1
     * node = 3, pre = 2
     * node = NULL, pre = 3
     * 递归返回
     * 返回当前头节点 pre = 3
     * 并且使当前节点node->next 指向 pre
     */
    ListNode* reverseList(ListNode* head) {
       return recursion(head,NULL);
    }
    ListNode* recursion(ListNode* node, ListNode* pre) {
        if(node == NULL){
            return pre;
        }
        ListNode* head = recursion(node->next,node);
        node->next = pre;
        return head;
    }
};
